using System;
using System.Collections.Generic;

namespace LannyPractiseCode
{
    /// <summary>
    /// 排序算法
    /// </summary>
    public class SearchHelper
    {
        //线性查找
        public static int SeqSearch(List<int> arr,int i)
        {
            foreach (var item in arr)
            {
                if(item==i)
                    return item;
            }

            return -1;
        }


        //二分查找(有序树中查找)
        public static int BinarySearch(List<int> arrs,int left,int right,int findValue)
        {
            if(left>right)
                return -1;
            
            int mid=(left+right)/2;
            if(arrs[mid]==findValue)
                return findValue;

            if(findValue>mid)
                return BinarySearch(arrs,mid+1,right,findValue);
            else if(findValue<mid)
                return BinarySearch(arrs,left,mid,findValue);
            else
                return -1;
        }
        //*课后思考题: {1,8,10，89,， 1000， 1000， 1234} 当一个有序数组中，
        //有多个相同的数值时，如何将所有的數值都查找到，比如这里的1000
        public static List<int> BinarySearch2(List<int> arrs,int left,int right,int findValue)
        {
            if(left>right)
                return new List<int>();
            
            int mid=(left+right)/2;
            if(findValue>mid)
                return BinarySearch2(arrs,mid+1,right,findValue);
            else if(findValue<mid)
                return BinarySearch2(arrs,left,mid,findValue);
            else
            {   
                List<int> retList=new List<int>();
                int temp=mid-1;
                while(true)
                {
                    if(temp<0  || arrs[temp]!=findValue)
                        break;
                    retList.Add(temp);
                    temp-=1;
                }

                retList.Add(mid);

                temp=mid+1;
                while(true)
                {
                    if(temp>arrs.Count  || arrs[temp]!=findValue)
                        break;
                    retList.Add(temp);
                    temp+=1;
                }

                return retList;
            }
                
        }

        //插值查找。。
        public static int InsertSearch(List<int> arrs,int left,int right,int findValue)
        {
            int mid=left+(right-left)*(findValue-arrs[left])/(arrs[right]-arrs[left]);
            int midVal=arrs[mid];
            if(findValue>midVal)
            {
                return InsertSearch(arrs,mid+1,right,findValue);
            }
            else if(findValue<midVal)
            {
                return InsertSearch(arrs,left,mid-1,findValue);
            }
            else
            {
                return mid;
            }
        }
    }
}